/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
  //递归边界：返回null
  if (preorder.length === 0 || inorder.length === 0) return null

  //构建根节点：先序遍历的第一个元素为根节点
  const rootVal = preorder[0]
  const root = new TreeNode(rootVal)

  //在中序遍历中寻找根节点的索引
  const index = inorder.indexOf(rootVal)
  //将中序遍历分割成左、右子树
  const leftTreeInorder = inorder.slice(0, index)
  const rightTreeInorder = inorder.slice(index + 1)
  // 将先序遍历分割成左右子树
  const leftTreePreorder = preorder.slice(1, leftTreeInorder.length + 1)
  const rightTreePreorder = preorder.slice(leftTreeInorder.length + 1)
  //递归构建左右子树
  root.left = buildTree(leftTreePreorder, leftTreeInorder)
  root.right = buildTree(rightTreePreorder, rightTreeInorder)

  //返回根节点
  return root
};